package tree.test106;

import listbyorder.utils.TreeNode;

import java.util.HashMap;

/**
 * 从中序与后序遍历序列构造二叉树
 *
 * @author code_yc
 * @version 1.0
 * @date 2020/7/16 12:17
 */
public class Solution1 {

    // DFS
    HashMap<Integer, Integer> map = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder == null || postorder.length == 0) return null;
        int n = postorder.length;
        for (int i = 0; i < n; i++) {
            map.put(inorder[i], i);
        }
        return dfs(postorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode dfs(int[] postorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr) return null;
        int c = postorder[pr];
        int k = map.get(c);
        TreeNode root = new TreeNode(c);
        root.right = dfs(postorder, inorder, pr - (ir - k), pr - 1, k + 1, ir);
        root.left = dfs(postorder, inorder, pl, pr - (ir - k) - 1, il, k - 1);
        return root;
    }
}
